package org.sunny.string;

import org.apache.commons.lang3.StringUtils;

/**
 * KMP算法
 *
 * @author Sunny
 * @date 2020/8/17
 */
public class KMP {

    public static void main(String[] args) {
        System.out.println(indexOf("Hello World", "H"));
        System.out.println(indexOf("Hello World", "d"));
        System.out.println(indexOf("Hello World", "or"));
        System.out.println(indexOf("Hello World", "ab"));
    }

    /**
     * KMP算法
     *  基于暴力匹配的逻辑优化
     *  增加next数组, 根据模式串的最大公共子串的长度判断移动索引的位置
     *
     * @param text 文本串
     * @param pattern 模式串
     * @author Sunny
     * @date 2020/8/17
     */
    public static int indexOf(String text, String pattern) {
        if (StringUtils.isBlank(text) || StringUtils.isBlank(pattern)) {
            return -1;
        }

        char[] textChars = text.toCharArray();
        char[] patternChars = pattern.toCharArray();

        int tlen = textChars.length;
        int plen = patternChars.length;

        if (tlen < plen) {
            return -1;
        }

        //获取next数组
        int[] next = next(pattern);
        int pi = 0, ti = 0;

        while (pi < plen && ti < tlen) {
            //pi < 0 的情况是模式串第一个字符就匹配失败, 拿到要移动索引为 -1
            if (pi < 0 || textChars[ti] == patternChars[pi]) {
                //当pi为-1时, pi++ 就 = 0, ti++ 移动一位继续比较
                pi++;
                ti++;
            } else {
                //根据next[pi]获取模式串中下一次比较字符的索引
                pi = next[pi];
            }
        }
        return pi == plen ? ti - pi : -1;
    }

    /**
     * 获取KMP中的next数组
     *
     * @param pattern 模式串
     * @author Sunny
     * @date 2020/8/17
     */
    private static int[] next(String pattern) {
        char[] chars = pattern.toCharArray();
        int[] next = new int[chars.length];

        int i = 0;
        //设置next[0]元素为-1
        int n = next[i] = -1;

        //制定遍历最大次数
        int iMax = chars.length - 1;
        while (i < iMax) {
            if (n < 0 || chars[i] == chars[n]) {

                //next数组优化
                ++i;
                ++n;

                //next[++i] = ++n;
                //如果 i+1 的字符与 n+1 的字符相等, 则可以优化掉 next[++i] 位置的++n, 直接指向 next[++n]
                //减少不必要的比较次数
                if (chars[i] == chars[n]) {
                    next[i] = next[n];
                } else {
                    n = next[n];
                }
            } else {
                next[i] = n;
            }
        }
        return next;
    }

    private static int[] next2(String pattern) {
        char[] chars = pattern.toCharArray();
        int[] next = new int[chars.length];

        int i = 0;
        //设置next[0]元素为-1
        int n = next[i] = -1;

        //制定遍历最大次数
        int iMax = chars.length - 1;
        while (i < iMax) {
            if (n < 0 || chars[i] == chars[n]) {
                next[++i] = ++n;
            } else {
                n = next[n];
            }
        }
        return next;
    }
}
